package com.cty._02_HighQualityCode._17_Print1ToMaxNDigits;

/**
 * @Auther: cty
 * @Date: 2020/7/5 9:27
 * @Description: 面试题17：打印1到最大的n位数
 * 题目：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则
 * 打印出1、2、3一直到最大的3位数即999。
 * @version: 1.0
 */
public class Print1ToMaxNDigits {

    /**
     * 累加实现打印从1到最大的n位十进制数
     * @param n
     */
    public static void print1ToMaxNDigits(int n){
        if(n <= 0)
            return;

        char[] number = new char[n];
        for(int i=0; i<n; i++)
            number[i] = '0';

        while(!increment(number)){
            printNumber(number);
        }
        System.out.println();
    }  // end Print1ToMaxNDigits()

    /**
     * 数字累加
     * @param number
     * @return
     *      当发生溢出返回 true
     */
    private static boolean increment(char[] number){
        boolean isOverflow = false;
        int length = number.length;
        int nTakeOver = 0;

        for(int i=length-1; i>=0; i--){
            int nSum = number[i] - '0' + nTakeOver;

            if(i == length-1)  // 最低位加1
                nSum++;

            if(nSum >= 10){
                if(i == 0)
                    isOverflow = true;
                else {
                    nTakeOver = 1;
                    nSum -= 10;
                    number[i] = (char) ('0' + nSum);
                }
            }else{
                number[i] = (char)('0' + nSum);
                break;
            }
        }  // end if

        return isOverflow;
    }  // end increment()

    /**
     * 从左边第一个不为0的位起打印数字
     * @param number
     */
    private static void printNumber(char[] number){
        boolean isBeginning0 = true;
        int length = number.length;

        for(int i=0; i<length; i++){
            if(isBeginning0 && number[i]!='0')
                isBeginning0 = false;

            if(!isBeginning0){
                System.out.print(number[i]);
            }
        }  // end for
        System.out.print(" ");
    }  // end printNumber()

    /**
     * 全排列实现打印从1到最大的n位十进制数
     * @param n
     */
    public static void print1ToMaxNDigits02(int n){
        if(n <= 0)
            return;

        char[] number = new char[n];

        for(int i=0; i<10; i++) {
            number[0] = (char)('0' + i);
            print1ToMaxNDigitsRecursively(number, n, 0);
        }
        System.out.println();
    }  // end print1ToMaxNDigits02()

    /**
     * 递归实现全排列
     * @param number
     * @param length
     * @param index
     */
    private static void print1ToMaxNDigitsRecursively(char[] number, int length, int index){
        if(index == length-1){
            printNumber(number);
            return;
        }

        for(int i=0; i<10; i++){
            number[index+1] = (char)('0' + i);
            print1ToMaxNDigitsRecursively(number, length, index+1);
        }
    }  // end print1ToMaxNDigitsRecursively()

}  // end class
